#include<iostream>
#include<ctime>
const int capacity=10;
class MinHeap
{
public:
    MinHeap():size(0){}
      void Insert(int value)
    {
        if(size==capacity)
            return;
        array[size]=value;
        sifwUp(size);
        size++;
    }
    void Remove()
    {
        if(size==0)
            return;
        array[0]=array[--size];
        siftDown(0);

    }
    int *GetRoot()
    {
        if(size==0)
            return nullptr;
        return &array[0];
    }
    void show()
    {
        for(int i=0;i<size;i++)
        {
            std::cout<<array[i]<<" ";
        }
        std::cout<<std::endl;
    }





private:
    int GetParent(int i){return(i-1)/2;}
    int GetLeftChild(int i){ return 2*i+1;}
    int GetRightChile(int i){return 2*i+2;}
     void sifwUp(int i)//上浮操作  O(logn)
    {
        while(i>0&&array[i]<array[GetParent(i)])
        {
            std::swap(array[i],array[GetParent(i)]);
            i=GetParent(i);
        }
    }
        void siftDown(int i)//下沉操作
    {
        int left=GetLeftChild(i);
        int right=GetRightChile(i);
        int min=i;
        if(left<size&&array[left]<array[min])
        {
            min=left;
        }
        if(right<size&&array[right]<array[min])
        {
            min=right;
        }
        if(min!=i)//i下沉了
        {
            std::swap(array[i],array[min]);
            siftDown(min);//递归下沉；
        }
    }
    int array[capacity];
    int size;
};

int main()
{
    //找出20个数的最大数
    srand(time(nullptr));
    int a[20]={0};
    for(int i=0;i<20;i++)
    {
        a[i]=std::rand()%100;
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    MinHeap h;
    for(int i=0;i<5;i++)
    {
          h.Insert(a[i]);
    }
  
    for(int i=5;i<20;i++)
    {
      if(a[i]>*h.GetRoot())
    {
        h.Insert(a[i]);
        h.Remove();
    }

    }
    h.show();



    return 0;
}
